#include <iostream>
#define number 8
using namespace std;

int data[number]={ 8, 4, 5, 6, 2, 1, 7, 3};

void mergesort( int start, int mid, int end ){
    int len1=mid - start + 1, len2 = end - mid;
    int i , j , k;
    cout<<endl<<len1<<endl<<len2<<endl;
    int* left = new int[len1];
    int *right = new int[len2];

    for( i = 0; i < len1 ; i++)
        left[i] = data[ start + i ];
    for ( i = 0 ; i < len2 ; i++)
        right[i] = data[ mid + 1 + i ];

    i = 0 ; j = 0;
    for( k = start ; k < end ; k ++){
        if( i == len1 || j == len2)
            break;
        if( left[i] <= right [j])
            data[k] = left[i++];
        else
            data[k] = right[j++];
    }
    while( i < len1)
        data[k++] = left[i++];
    while( j < len2)
        data[k++] = right[j++];
    delete left;
    delete right;

//    cout<<endl;
    for(i = start ; i < end+1 ; i++)
        cout<<data[i]<<"   ";
    cout<<endl;
}

void merge( int start, int end){
    if( start < end) {
        int mid = (start + end )/2;
        merge(start , mid);
        merge(mid + 1, end);
        mergesort( start, mid ,end);
    }
}

int main(){
    merge(0, number-1);
}
